//简单版
void levelOrder(TreeNode* root) 
{
   //边界情况:空树
   if(root==nullptr)
       return {};
   queue<TreeNode*> q;				//队列
   q.push(root); 					//先入根结点           
   while(!q.empty())
   {
		//出队列，并且让他们孩子入队
          TreeNode* front=q.front();  
          q.pop();
          //访问结点
          cout<<front->val<<" ";
          //入左节点
          if(front->left)
              q.push(front->left);
          //入右节点
          if(front->right)
              q.push(front->right);
    }
}
//力扣1
vector<vector<int>> levelOrder(TreeNode* root) {
    //边界情况
    if(root==nullptr)
        return {};
    vector<vector<int>> vv;         //保存所有的遍历结果
    queue<TreeNode*> q;
    q.push(root); 
    //第一层只有一个孩子
    int LevelSize=1;            
    while(!q.empty())
    {
    	vector<int> v;                  //保存每层的数据
        //记录每层有多少个孩子
        while(LevelSize--)
		{
			//出队列，并且让他们孩子入队
           TreeNode* front=q.front();  
           q.pop();
           v.push_back(front->val);
           //入左节点
           if(front->left)
               q.push(front->left);
           //入右节点
           if(front->right)
               q.push(front->right);
        }
        LevelSize=q.size();     //更新每层孩子个数
        vv.push_back(v);        //把每层的访问数据插入二维数组
     }
    return vv;
}


//力口锯齿形
vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
{
     //边界情况:空树
     if(root==nullptr)
         return {};
     vector<vector<int>> vv;         //保存所有的遍历结果
     queue<TreeNode*> q;
     q.push(root); 
     bool flag=false;
     //第一层只有一个孩子
     int LevelSize=1;            
     while(!q.empty())
     {
         vector<int> v;                  //保存每层的数据
         //记录每层有多少个孩子
         while(LevelSize--)
         {
             //出队列，并且让他们孩子入队
             TreeNode* front=q.front();  
             q.pop();
             v.push_back(front->val);
             //入左节点
             if(front->left)
                 q.push(front->left);
             //入右节点
             if(front->right)
                 q.push(front->right);
         }
         LevelSize=q.size();     //更新每层孩子个数
         //判断是不是要反转
         if(flag)
             reverse(v.begin(),v.end());
         vv.push_back(v);        //把每层的访问数据插入二维数组
         flag=!flag;			//间隔一层反转
     }
     return vv;
 }

